Nowadays, the development of robot still puts emphasis on designs of mechanism, motion and path planning, and navigation. The other extensive and relevant inventions, such as face-recognition, voice-recognition, dactylogram-recognition and so on, belong to the scope of robots' physical motion and perceptive analysis. However, there are many limitations to apply robots to security industry so that robots usually take auxiliary jobs. As to the execution of security patrols, at present robots perform patrols for important site or random patrols for a whole region, but there is no integrated invention or discussion about a complete patrol for movements and paths. In security industry, a patrol duty performed by a robot is a fundamental and important ability. If a meaningful patrol path planning is based on geographical features of a patrol place, a self-conscious security robot can perform the patrol duties more efficiently to reduce the probabilities of invasion and property loss. When artificial intelligence, motion controlling and various algorithms for robots become more and more mature, the patrol path planning will be a critical problem for mankind. There are several methods for planning patrol paths among the present prior arts.
Using Potential Field is one of the common patrol paths planning methods for robots, and the method treats the whole environment as a potential field. A potential could be defined as an obstacle of the environment, a probability of chasing a target's location, or an unexplored region. When a trend of the potential is used to plan a route for robots, a location with high potential means a location of a obstacle. (G. Dozier, A. et al. 1998)
Markov Decision Processes (MDP) and Partially Observable Markov Decision Processes (POMDPs) for dynamic decisions to process simple path decisions and self-learning of robots are the common patrol paths planning methods. It is noted that parts of results of the methods are random and the other parts are made by the decisions.
Other inventions relating to patrol path planning include Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP, Vigo 2001). TSP method is mainly used for a salesman to seek the shortest route that the salesman starts from an initial node, pass all nodes and then return to the initial node. VRP method is to seek a problem of deliver path planning for one or several vehicles, such as a route plan for a city bus. Although there are several prior arts as the above patrol path planning methods, there is no patrol path planning methods based on a graph at present.
Therefore, it would be useful to invent a patrol device and a patrol path planning method to circumvent all the above issues. In order to fulfill this need the inventors have proposed an invention “PATROL DEVICE AND PATROL PATH PLANNING METHOD FOR THE SAME.”